<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
  <title>C++ Tutorial: Quiz - Bit Manipulation</title>
  <meta
 content="C++ Tutorial: Quiz - Bit Manipulation"
 name="description" />
  <meta
 content="C++ Tutorial, Quiz - Bit Manipulation, Interview Questions, Two's Complement"
 name="keywords" />
  <meta http-equiv="Content-Type"
 content="text/html; charset=ISO-8859-1" />
  <link type="text/css" rel="stylesheet" href="../images/bogostyleWidePre.css" />
</head>
<body>
<div id="page" align="center">
<div id="content" style="width: 800px;">
<div id="logo">
<div class="whitetitle" style="margin-top: 70px;">bogotobogo </div>
</div>
<div id="topheader">
<div class="headerbodytext" align="left"><br />
<strong>Bogotobogo</strong><br />
contact@bogotobogo.com </div>
<div class="smallgraytext" id="toplinks"><a href="../index.html">Home</a>
| <a href="../sitemap.html">Sitemap</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="menu">
<div class="smallwhitetext" style="padding: 9px;" align="right"><a
 href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">Products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="../blog" target="_blank">Contact Us</a>
</div>
</div>
<div id="submenu">
<div class="smallgraytext" style="padding: 9px;" align="right">
<a href="../gif.html">Gif</a> 
|<a href="../java_applet.html">JavaApplet/Web Start</a>
| <a href="../flash.html">Flash</a>
| <a href="../shockwave.html">ShockWave</a>
| <a href="../svg.html">SVG</a>
| <a href="../iPhone.html">iPhone/iPad</a>
| <a href="../android.html">Android</a>
| <a href="../OnHTML5.html">HTML5</a>
| <a href="../Algorithms/algorithms.html">Algorithms</a>
| <a href="../News/NewsMain.html">News</a>
| <a href="../cplusplus/cpptut.html">C++</a>
| <a href="../Java/tutorial/on_java.html">Java</a>
| <a href="../php/phptut.html">PHP</a>
| <a href="../DesignPatterns/introduction.html">Design Patterns</a>
| <a href="../python/pytut.html">Python</a> 
| <a href="../CSharp/.netframework.html">C#</a>
| <a href="../forums.html">Forums</a> 
| <a href="../VisualBasicSQL/introduction.html">Visual Basic</a>
</div>
</div>


<div id="contenttext">
<br />
<br />
<!-- Use of this code assumes agreement with the Google Custom Search Terms of Service. -->
<!-- The terms of service are available at http://www.google.com/cse/docs/tos.html -->
<form name="cse" id="searchbox_demo" action="http://www.google.com/cse">
  <input type="hidden" name="cref" value="" />
  <input type="hidden" name="ie" value="utf-8" />
  <input type="hidden" name="hl" value="" />
  <input name="q" type="text" size="40" />
  <input type="submit" name="sa" value="Search" />
</form>
<script type="text/javascript" src="http://www.google.com/cse/tools/onthefly?form=searchbox_demo&lang="></script>


<div id="bookmarkshare">
<script type="text/javascript">var addthis_config = {"data_track_clickback":true};</script>
<a class="addthis_button" href="http://www.addthis.com/bookmark.php?v=250&amp;username=khhong7"><img src="http://s7.addthis.com/static/btn/v2/lg-share-en.gif" width="125" height="16" alt="Bookmark and Share" style="border:0"/></a><script type="text/javascript" src="http://s7.addthis.com/js/250/addthis_widget.js#username=khhong7"></script>
</div>


<br />
<br />
<br />
<br />
<div style="padding: 10px;"><span class="titletext">C++ Tutorial <br />
Quiz - Bit Manipulation</span></div>

<img src="../images/cplusplus/cpp_logo.jpg" alt="cplusplus logo"/>

<br />
<br />
<div class="bodytext" style="padding: 12px;" align="justify"> 
<div class="subtitle_2nd" id="SubList">List of C++ Tutorials</div>
<ul>
   <li><a href="cpptut.html">C++ Home</a> </li>
   <li><a href="string.html">String</a> </li>
   <li><a href="constructor.html">Constructor</a> </li>
   <li><a href="operatoroverloading.html">Operator Overloading</a></li> 
   <li><a href="virtualfunctions.html">Virtual Functions</a></li>
   <li><a href="dynamic_cast.html">Dynamic Cast Operator</a></li>
   <li><a href="typecast.html">Type Cast Operators</a></li>
   <li><a href="autoptr.html">Class auto_ptr</a></li>
   <li><a href="templates.html">Templates</a></li>
   <li><a href="references.html">References for Built-in Types</a></li>
   <li><a href="valuevsreference.html">Pass by Value vs. Pass by Reference</a></li>
   <li><a href="memoryallocation.html">Memory Allocation</a></li>
   <li><a href="friendclass.html">Friend Functions and Friend Classes</a></li>
   <li><a href="functors.html">Functors (Function Objects)</a></li>
   <li><a href="statics.html">Static Variables and Static Class Members</a></li>
   <li><a href="exceptions.html">Exceptions</a></li>
   <li><a href="pointers.html">Pointers</a></li>
   <li><a href="pointers2.html">Pointers II - void*, Pointer/Array, and Pointer to Pointer</a></li>
   <li><a href="pointers3.html">Pointers III - Pointer to Function, Null Pointer</a></li>
   <li><a href="assembly.html">Taste of Assembly</a></li>
   <li><a href="smallprograms.html">Small Programs</a></li>
   <li><a href="linkedlist.html">Linked List Examples</a></li>
   <li><a href="binarytree.html">Binary Tree Example Code</a></li>
   <li><a href="stl.html">Standard Template Library (STL)</a></li>
   <li><a href="stl2.html">Standard Template Library (STL) II - Maps</a></li>
   <li><a href="stl3_iterators.html">Standard Template Library (STL) III - Iterators</a></li>
   <li><a href="slicing.html">Object Slicing and Virtual Table</a></li>
   <li><a href="this_pointer.html">The this Pointer</a></li>
   <li><a href="stackunwinding.html">Stack Unwinding</a></li>
   <li><a href="upcasting_downcasting.html">Upcasting and Downcasting</a></li>
   <li><a href="object_returning.html">Object Returning</a></li>
   <li><a href="private_inheritance.html">Private Inheritance</a></li>
   <li><a href="cplusplus_keywords.html">C++_Keywords</a></li>
   <li><a href="multithreaded.html">Multi-Threaded Programming - Terminology</a></li>
   <li><a href="multithreaded2A.html">Multi-Threaded Programming II - Native Thread for Win32 (A) </a></li>
   <li><a href="multithreaded2B.html">Multi-Threaded Programming II -  Native Thread for Win32 (B) </a></li>
   <li><a href="multithreaded2C.html">Multi-Threaded Programming II -  Native Thread for Win32 (C) </a></li>
   <li><a href="multithreaded2.html">Multi-Threaded Programming II - C++ Thread for Win32</a></li>
   <li><a href="multithreaded3.html">Multi-Threaded Programming III - C++ Class Thread for Pthreads</a></li>
   <li><a href="multithreadedDebugging.html">Multithread Debugging</a></li>
   <li><a href="embeddedSystemsProgramming.html">Embedded Systems Programming</a></li>
   <li><a href="boost.html">Boost</a></li>
   <li>Programming Questions and Solutions
    <ul>
       <li><a href="quiz_strings_arrays.html">Strings and Arrays</a></li>
       <li><a href="quiz_linkedlist.html">Linked List</a></li>
       <li><a href="quiz_recursion.html">Recursion</a></li>
       <li><a href="quiz_bit_manipulation.html">Bit Manipulation</a> </li>
       <li><a href="google_interview_questions.html">140 Google Interview Questions</a> </li>
    </ul>
   </li>

</ul>
</div>
<br />

<br />
<img src="images/quiz/DoSanSuhWon.png" alt="DoSanSuhWon"/>
<br />
<br />
<br />

<div class="bodytext" style="padding: 12px;" align="justify"> 
<div class="subtitle_2nd" id="SubList">List of codes</div>
<ul>
   <li> <a href="#bitwiseoperations">Bitwise Operations</a> </li>
   <li> <a href="#setclear">Setting and Clearing a Bit</a> </li>
   <li> <a href="#displaybit">Displaying an Integer with Bits</a> </li>
   <li> <a href="#dectohex">Converting Decimal to Hex</a> 
</li>
   <li><a href="#bitcount">The Number of Bits Set in an Integer (Number of Ones)</a> </li>
   <li><a href="#bitsetpos">The Bit Set Position of an Integer</a> </li>
   <li><a href="#swap">In-Place Integer Swap with Bit Manipulation</a> </li>
   <li><a href="#numberofbits">The Number of Bits Required to Convert an Integer A to Integer B</a> </li>
   <li><a href="#swapevenodd">Swap Odd and Even Bits in an Integer</a> </li>
   <li><a href="#powerof2">What (n &#38 (n-1) == 0) is checking? </a></li>
   <li><a href="#twoscomplement">Two's Complement</a></li>
   <li><a href="#bit_flip">Fliping n-th bit of an integer</a></li>
   <li><a href="#floating_bit_pattern">Floating Point Number Bit Pattern</a></li>
   <li><a href="#int_palindrome">Bit pattern palindrome of an integer </a></li>
</ul>
</div>


<div class="bodytext" style="padding: 12px;" align="justify"> 
<div class="subtitle" id="bitmanipulation">Codes - Bit Manipulation</div>
<br />
<div class="subtitle_2nd" id="bitwiseoperations">Bitwise Operations</div>
<br />
<table border="2", cellpadding="5">
<tr>
<td>~</td>
<td>complement</td>
<td>Bit <strong>n</strong> of <strong>~x</strong> is the opposite of bit <strong>n</strong> of <strong>x</strong></td>
</tr>
<tr>
<td>&</td>
<td>Bitwise And</td>
<td>Bit <strong>n</strong> of <strong>x&y</strong> is 1 if bit <strong>n</strong> of <strong>x</strong> and bit <strong>n</strong> of <strong>y</strong> is 1. </td>
</tr>
<tr>
<td>|</td>
<td>Bitwise Or</td>
<td>Bit <strong>n</strong> of <strong>x|y</strong> is 1 if bit <strong>n</strong> of <strong>x</strong> or bit <strong>n</strong> of <strong>y</strong> is 1. </td>
</tr>
<tr>
<td>^</td>
<td>Bitwise Exclusive Or</td>
<td>Bit <strong>n</strong> of <strong>x^y</strong> is 1 if bit <strong>n</strong> of <strong>x</strong> or bit <strong>n</strong> of <strong>y</strong> is 1 but not if both are 1. </td>
</tr>
<tr>
<td>>></td>
<td>Right Shift (divide by 2)</td>
<td>Bit <strong>n</strong> of <strong>x>>s</strong> is bit <strong>n-s</strong> of <strong>x</strong>. </td>
</tr>
<tr>
<td><<</td>
<td>Left Shift (multiply by 2)</td>
<td>Bit <strong>n</strong> of <strong>x&lt;&lt;s</strong> is bit <strong>n+s</strong> of <strong>x</strong>. </td>
</tr>
</table> 
<br />
<br />

<p><strong>bitwise Complement: </strong> The bitwise complement operator, the <strong>tilde</strong>, <strong>~</strong>, flips every bit. The tilde is sometimes called a <strong>twiddle</strong>, and the bitwise complement twiddles every bit:
</p>
<p>This turns out to be a great way of finding the largest possible value for an unsigned number: </p>
<pre>
unsigned int max = ~0;
</pre>
<br />


<p><strong>bitwise AND: </strong> The bitwise <strong>AND</strong> operator is a single ampersand: <strong>&</strong>:
 </p>
<pre>
01001000 & 
10111000 = 
--------
00001000
</pre>
<br />


<p><strong>bitwise OR: </strong> The bitwise <strong>OR</strong> operator is a <strong>|</strong>:
 </p>
<pre>
01001000 | 
10111000 = 
--------
11111000
</pre>
<br />


<p><strong>bitwise Exclusive OR (XOR): </strong> The <strong>exclusive-or</strong> operation takes two inputs and returns a 1 if either one or the other of the inputs is a 1, but not if both are. That is, if both inputs are 1 or both inputs are 0, it returns 0. Bitwise exclusive-or, with the operator of a carrot, <strong>^</strong>, performs the exclusive-or operation on each pair of bits. Exclusive-or is commonly abbreviated <strong>XOR</strong>. </p>
<pre>
01110010 ^
10101010 
--------
11011000
</pre>
<p>Suppose, we have some bit, either 1 or 0, that we'll call Z. When we take Z <strong>XOR</strong> 0, then we always get Z back: if Z is 1, we get 1, and if Z is 0, we get 0. On the other hand, when we take Z <strong>XOR</strong> 1, we flip Z. If Z is 0, we get 1; if Z is 1, we get 0:</p>
<ul>	
	<li><strong>myBits ^ 0</strong> : No change</li>
	<li><strong>myBits ^ 1</strong> : Flip <br />
	It's a kind of selective <strong>twiddle(~).</strong>.<br />
	So, if we do <strong>XOR</strong> against <strong>111...1111</strong>, all the bits of <strong>myBits</strong> flipped. It's equivalent of doing <strong>twiddle(~).</strong>.
	</li>
</ul>
<p>Another interesting trick using the <strong>XOR</strong>: It does in place swap of integers.<br />
 If we apply the <strong>XOR</strong> operation twice -- say we have a bit, A, and another bit B, and we set C equal to A <strong>XOR</strong> B, and then take C <strong>XOR</strong> B: we get A <strong>XOR</strong> B <strong>XOR</strong> B, which essentially either flips every bit of A twice, or never flips the bit, so we just get back A. (We can also think of B <strong>XOR</strong> B as cancelling out.) As an exercise, can we think of a way to use this to exchange two integer variables without a temporary variable? <br />
Check <a href=quiz_bit_manipulation.html#swap>In-Place Integer Swap with Bit Manipulation</a>.</p>
<br />


<p><strong>rightshift operator (>>): </strong> Moving all the bits of a number a specified number of places to the right. Note that a bitwise right-shift will be the equivalent of integer division by 2:</p>
<pre>
00000101(5)  >>  1
--------
00000010(2)
</pre>
<br />


<p><strong>leftshift operator (<<): </strong> Moving all the bits of a number a specified number of places to the left: </p>
<pre>
[myVariable]<<[number of places]
</pre>
<p>Suppose we have number 8 written in binary 00001000. If we wanted to shift it to the left 2 places, we'd end up with 00100000; everything is moved to the left two places, and zeros are added as padding. This is the number 32:</p>
<pre>
00001000(8)  <<  2
--------
00100000(32)
</pre>
 <p>Actually, left shifting is the equivalent of <strong>multiplying by a power of two</strong>:</p>
<pre>
x << n
--------
x * (1 << n)
</pre>
<p>More specifically:</p>
<pre>
8 << 2
--------
8 * (1 << 2)
--------
32
</pre>

<br />


<p><strong>Set</strong> a bit (where n is the bit number, and 0 is the least significant bit):</p>
<pre>
 unsigned char a |= (1 << n);
</pre>
<p>Example:</p>
<pre>
a               1 0 0 0 0 0 0 0
a |= (1 << 1) = 1 0 0 0 0 0 1 0
a |= (1 << 3) = 1 0 0 0 1 0 0 0
a |= (1 << 5) = 1 0 1 0 0 0 0 0
</pre>
<br />


<p>
<strong>Clear</strong> a bit:</p>
<pre>
 unsigned char b &= ~(1 << n);
</pre>
<p>Example:</p>
<pre>
b                1 1 1 1 1 1 1 1
b &= ~(1 << 1) = 1 1 1 1 1 1 0 1
b &= ~(1 << 3) = 1 1 1 1 0 1 1 1
b &= ~(1 << 5) = 1 1 0 1 1 1 1 1
</pre>
<br />


<p>
<strong>Toggle</strong> a bit:</p>
<pre>
 unsigned char c ^= (1 << n);
</pre>
<p>Example:</p>
<pre>
c               1 0 0 1 1 0 1 1
c ^= (1 << 1) = 1 0 0 1 1 0 0 1
c ^= (1 << 3) = 1 0 0 1 0 0 1 1
c ^= (1 << 5) = 1 0 1 1 1 0 1 1
</pre>
<br />


<p>
<strong>Test</strong> a bit:
</p>
<pre>
 unsigned char e = d & (1 << n); //d has the byte value.
</pre>
<br />
<br />

<div class="subtitle_2nd" id="setclear">Setting and Clearing a Bit</div>
<p>The code below shows how to set or clear a bit of an integer.</p>
<pre>
#include &lt;iostream&gt;

using namespace std;

void binary(unsigned int n)
{
	for(int i = 256; i > 0; i = i/2) {
		if(n & i) 
			cout << " 1";
		else
			cout << " 0";
	}
	cout << endl;
}

bool getBit(int n, int index)
{
	return ( (n & (1 << index) ) > 0);
}

int setBit(int n, int index, bool b)
{
	if(b)
		return (n | (1 << index)) ;	
	else {
		int mask = ~(1 << index);
		return n & mask;
	}
}

int main()
{
	int num, index;

	num = 16;

	cout << "Input" << endl;
	for (int i = 7; i >= 0; i--) 
		cout << getBit(num,i) << " ";
	cout << endl;

	/* set bit */
	index = 6;
	cout << "Setting " << index << "-th bit" << endl;
	num = setBit(num, index, true);
	for (int i = 7; i >= 0; i--) 
		cout << getBit(num,i) << " ";
	cout << endl;

	/* unset (clear) bit */
	index = 4;
	cout << "Unsetting (Clearing) " << index << "-th bit" << endl;
	num = setBit(num, index, false);
	for (int i = 7; i >= 0; i--) 
		cout << getBit(num,i) << " ";
	cout << endl;

	return 0;
}
</pre>
<p>Output is:</p>
<pre>
Input
0 0 0 1 0 0 0 0
Setting 6-th bit
0 1 0 1 0 0 0 0
Unsetting (Clearing) 4-th bit
0 1 0 0 0 0 0 0
</pre>



<br />
<br />

<div class="subtitle_2nd" id="displaybit">Displaying an Integer with Bits</div>
<pre>
#include &lt;iostream&gt;
#include &lt;iomanip&gt;
using namespace std; 
 
void binary(unsigned int u) 
{ 
	int upper;
	if(u < 256)
		upper = 128;
	else
		upper = 32768;

	cout << setw(5) << u << ": ";
	for(int i = upper; i > 0; i = i/2) {
		if(u & i) 
			cout << "1 "; 
		else 
			cout << "0 "; 
	}
	cout << "\n"; 
}

int main() 
{
	binary(5);
	binary(55);
	binary(255);
	binary(4555);
	binary(14555);
	return 0;
}
</pre>
<p>Output is:</p>
<pre>
    5: 0 0 0 0 0 1 0 1
   55: 0 0 1 1 0 1 1 1
  255: 1 1 1 1 1 1 1 1
 4555: 0 0 0 1 0 0 0 1 1 1 0 0 1 0 1 1
14555: 0 0 1 1 1 0 0 0 1 1 0 1 1 0 1 1
</pre>

<br />
<br />
<div class="subtitle_2nd" id="dectohex">Converting Decimal to Hex</div>
<pre>
#include &lt;iostream&gt;
using namespace std;

/* hex with leading zeros */
void decToHex(int n)
{
	char *hexString = "0123456789ABCDEF";

	cout << "decimal: " << n << endl;    
	cout << "hex    : ";
	for (int i = 2*sizeof(int) - 1; i >= 0; i--)
            cout << hexString[(n >> i*4) & 0xF];
	cout << endl << endl;
}

int main() {
	decToHex(10);
	decToHex(100);
	decToHex(1000);
	return 0;
}
</pre>
<p>Output is:</p>
<pre>
decimal: 10
hex    : 0000000A

decimal: 100
hex    : 00000064

decimal: 1000
hex    : 000003E8
</pre>
<br />
<br />


<div class="subtitle_2nd" id="bitcount">The Number of Bits Set in an Integer (Number of Ones)</div>
<p>This code gets the number of bits set to 1 in an integer. In other words, it counts the number of one. </p>
<p><strong>bitCountA()</strong> is an O(n), where n is the size, in bits, of an integer, while <STRONG>bitCountB()</strong> is an O(m), where m is the number of 1's in the solution. </p>

<pre>
#include &lt;iostream&gt;

using namespace std;

void binary(unsigned int n)
{
	int upper = 256;
	for(int i = upper; i > 0; i = i/2) {
		if(n & i) 
			cout << " 1";
		else
			cout << " 0";
	}
	cout << endl;
}

/* O(n), where n is the size, in bits, of an integer */
int bitCountA(int n)
{
	int count = 0;
	while(n) {
		if(n & 1) count++;
		n = n >> 1;
	}
	return count;
}

/* O(m), where m is the number of 1's in the solution. */
int bitCountB(int n)
{
	int count = 0;
	while(n) {
		n = n & (n-1);
		count++;
	}
	return count;
}


int main()
{
	int a;

	a = 250;
	binary(a);
	cout << "Bit count = " << bitCountA(a) << endl;

	a = 250;
	binary(a);
	cout << "Bit count = " << bitCountB(a) << endl;
	return 0;
}
</pre>
<p>Output is:</p>
<pre>
 0 1 1 1 1 1 0 1 0
Bit count = 6
 0 1 1 1 1 1 0 1 0
Bit count = 6
</pre>
<br />
<br />

<div class="subtitle_2nd" id="bitsetpos">The Bit Set Position of an Integer</div>
<p>This code stores the positions of bits set to 1 in an integer.</p>
<pre>
#include &lt;iostream&gt;

using namespace std;

void binary(unsigned int n)
{
	for(int i = 256; i > 0; i = i/2) {
		if(n & i) 
			cout << " 1";
		else
			cout << " 0";
	}
	cout << endl;
}

int bitCount(int n)
{
	int count = 0;
	while(n) {
		if(n & 1) count++;
		n = n >> 1;
	}
	return count;
}

void bitSetPos(int n, int a[])
{
	int ic = 0;
	for(int i = 0; i < 32; i++) {
		if(n & 1) a[ic++] = i;
		n = n >> 1;
	}
}

int main()
{
	int num = 100;
	int bc, nbit;
	int *a;

	/* get bit count */
	nbit = bitCount(num);
	/* array to store the bit set postion */
	a = new int[nbit];
	/* display the integer in bits */
	binary(num);
	/* get the position of bit set */
	bitSetPos(num,a);

	cout << "bit set position " << endl;
	for(int i = 0; i < nbit; i++) {
		cout << a[i] << " ";
	}
	cout << endl;

	delete [] a;

	return 0;
}
</pre>
<p>Output is:</p>
<pre>
 0 0 1 1 0 0 1 0 0
bit set position
2 5 6
</pre>

<br />
<br />
<div class="subtitle_2nd" id="swap">In-Place Integer Swap with Bit Manipulation</div>
<p>This code swaps two integers in place using exclusive or (xor).</p>
<pre>
#include &lt;iostream&gt;

using namespace std;

void inplace_swap_A(int &a, int &b)
{
	a = b - a;
	b = b - a;
	a = a + b;
}

// Using xor property: a^b^b => a
void inplace_swap_B(int &a, int &b)
{
	a = a ^ b;	// a holds a_old ^ b_old
	b = a ^ b;	// b holds a_old which is (a_old ^ b_old) ^ b_old
	a = a ^ b;	// this line means a <--  (a_old ^ b_old) ^ a_old 
			// since b holds a_old.
			// So, as a result, a gets the value of b_old.
}

int main()
{
	int a = 10, b = 20;
	cout << "init values:  a = " << a << " b = " << b << endl;

	inplace_swap_A(a,b);
	cout << "swap A:  a = " << a << " b = " << b << endl;

	a = 100, b = 200;
	cout << "init values:  a = " << a << " b = " << b << endl;

	inplace_swap_B(a,b);
	cout << "swap B:  a = " << a << " b = " << b << endl;

	return 0;
}
</pre>
<p>Output from the run is: </p>
<pre>
init values:  a = 10 b = 20
swap A:  a = 20 b = 10
init values:  a = 100 b = 200
swap B:  a = 200 b = 100
</pre>


<br />
<br />


<div class="subtitle_2nd" id="numberofbits">The Number of Bits Required to Convert an Integer A to Integer B</div>
<p>This problem is surprisingly straightforward. <br />
It's just a matter of figuring out which bits in two numbers are different. <br />
It's an exclusive or, xor.</p>

<pre>
#include &lt;iostream&gt;
#include &lt;iomanip&gt;
using namespace std; 
 
int convertAtoB(int a, int b) 
{ 
	int c = a ^ b;
	int count = 0;

	while(c != 0) {
		count += c & 1;
		c = c >> 1;
	}
	return count;
}

void binary(unsigned int u) 
{ 
	int upper;
	if(u < 256)
		upper = 128;
	else
		upper = 32768;

	cout << setw(3) << u << ": ";
	for(int i = upper; i > 0; i = i/2) 
		if(u & i) 
			cout << "1 "; 
		else 
			cout << "0 "; 
	cout << "\n"; 
}

int main() 
{
	int a,b;
	a = 8;
	b = 4;
	binary(a);binary(b);
	cout << "# of bit required = " << convertAtoB(a,b) << endl;
	cout << endl;

	a = 128;
	b = 25;
	binary(a);binary(b);
	cout << "# of bit required = " << convertAtoB(a,b) << endl;
	cout << endl;

	a = 10;
	b = 254;
	binary(a);binary(b);
	cout << "# of bit required = " << convertAtoB(a,b) << endl;
	cout << endl;

	return 0;
}
</pre>
<p>Output is:</p>
<pre>
  8: 0 0 0 0 1 0 0 0
  4: 0 0 0 0 0 1 0 0
# of bit required = 2

128: 1 0 0 0 0 0 0 0
 25: 0 0 0 1 1 0 0 1
# of bit required = 4

 10: 0 0 0 0 1 0 1 0
254: 1 1 1 1 1 1 1 0
# of bit required = 5
</pre>
<br />
<br />


<div class="subtitle_2nd" id="swapevenodd">Swap Odd and Even Bits in an Integer</div>
<p>Masking even bits with 0xaa, then shift right. Mask odd bits with 0x55, then shift left. Then OR them. </p>
<pre>
#include &lt;iostream&gt;
#include &lt;iomanip&gt;
using namespace std; 
 
void binary(unsigned int u) 
{ 
	int upper;
	if(u < 256)
		upper = 128;
	else
		upper = 32768;

	cout << setw(3) << u << ": ";
	for(int i = upper; i > 0; i = i/2) 
		if(u & i) 
			cout << "1 "; 
		else 
			cout << "0 "; 
	cout << "\n"; 
}

int swapEvenOddBits(int n)
{
	return ( ((n & 0xaa) >> 1) | ((n & 0x55) << 1) );
}

int main() 
{
	int n = 180;

	cout << "Original integer" << endl;
	binary(n);
	cout << endl;
	cout << "Ending with 0xaa" << endl;
	binary(n & 0xaa);
	cout << endl;
	cout << "Right shift for even bits" << endl;
	binary((n & 0xaa) >> 1);
	cout << endl;
	cout << "Ending with 0x55" << endl;
	binary(n & 0x55);
	cout << endl;
	cout << "Left shift for odd bits" << endl;
	binary((n & 0x55) << 1);
	cout << endl;

	cout << "Call swapEvenOddBits" << endl;

	/* Swap bits */
	binary(  swapEvenOddBits(n)  );

	return 0;
}
</pre>
<p>Output is:</p>
<pre>
<br />Original integer
180: 1 0 1 1 0 1 0 0

Ending with 0xaa
160: 1 0 1 0 0 0 0 0

Right shift for even bits
 80: 0 1 0 1 0 0 0 0

Ending with 0x55
 20: 0 0 0 1 0 1 0 0

Left shift for odd bits
 40: 0 0 1 0 1 0 0 0

Call swapEvenOddBits
120: 0 1 1 1 1 0 0 0
</pre>
<br />
<br />


<div class="subtitle_2nd" id="powerof2">What (n &#38 (n-1) == 0) is checking? </div>
<p><strong>n &#38 (n-1) == 0</strong> means that <strong>n</strong> and <strong>n-1</strong> never share a 1 for any bits.</p>
<p>So, for example, suppose <strong>n</strong> and <strong>n-1</strong> look like this.</p>
<pre>
n   = abcde1000
n-1 = abcde0111
</pre>
<p>abcde must be all 0s, which means that <strong>n</strong> must look like:</p>
<pre>
000001000
</pre>
<p><strong>n</strong> is a power of two.</p>
<p>So, <strong>(n &#38 (n-1) == 0)</strong> is checking if <strong>n</strong> is a <strong>power of 2</strong>.</p>
<br />
<br />


<div class="subtitle_2nd" id="twoscomplement">Two's Complement</div>
<p>In computer, every bit is mapped representing something. Let's limit our discussion to 8 bits (1 byte). The number <strong>7</strong> is expressed by the following bit pattern:</p>
<pre>
00000111 (7)
</pre>
<p>How about <strong>-7</strong>? If we use the <strong>Most Significant Bit (MSB)</strong> as a sign bit, and let the value of <strong>1</strong> represent (-) sign. Then, <strong>-7</strong> will have the following bit pattern:</p>
<pre>
10000111 (-7)
</pre> 
<p>However, when we do an addition of the two, it does not become 0:</p>
<pre>
00000111 +
10000111
--------
10001110 
</pre>
<p>So, how we make the sum of the two be zero?</p>
<pre>
00000111 +
1xxxxxxx
--------
00000000 
</pre>
<p>We can find the x's easily:</p>
<pre>
00000111 +
<font color="red">11111001</font>
--------
00000000 
</pre>
<p>Notice that we can get 
<pre>
<font color="red">11111001</font>
</pre>
by adding <strong>1</strong> after <strong>inverting</strong> all the bits in <strong>00000111 (7)</strong>:</p>
<pre>
11111000 +
00000001
--------
<font color="red">11111001</font>
</pre>
<p><strong>Invert a bit pattern</strong> of a number, and then <strong>add</strong> 1. The resulting number is the <strong>two's complement</strong> of the number.</p>
<p>
So, the <strong>two's complement</strong> satisfies basic arithmetic, but <strong>one's complement</strong> (The resulting number by changing just the sign bit) does not.</p>
<p>Here is an additional question.<br />
What's the representation of bit pattern for <strong>short -1</strong>? <br />
Hint: adding 1 should turn off all the bits and short needs 2 bytes. </p>
<p>The answer is <strong>11111111 11111111</strong>.</p>
<br />
<br />
<br />


<div class="subtitle_2nd" id="bit_flip">Fliping n-th bit of an integer</div>
<p>This example is for the <a href="smallprograms.html#endian" target="_blank">little-endian</a> byte order case. <br />
Note that <strong>XOR</strong> against <strong>1</strong> flips a bit. Check <a href="#bitwiseoperations">Bitwise Operations</a> </p>
<pre>
#include &lt;iostream&gt;
#include &lt;iomanip&gt;
using namespace std; 
 
void binary(unsigned int u) 
{ 
	int upper;
	if(u < 256)
		upper = 128;
	else
		upper = 32768;

	cout << setw(5) << u << ": ";
	for(int i = upper; i > 0; i = i/2) {
		if(u & i) 
			cout << "1 "; 
		else 
			cout << "0 "; 
	}
	cout << "\n"; 
}

void bit_flip(int& m, int nth)
{
	m ^= 1 << nth;
}

int main() 
{
	int m = 12;
	int nth = 2;
	binary(m);
	cout << "   flip " << nth << "th bit of " << m << endl;
	bit_flip(m,nth);
	binary(m);
	cout << endl;

	m = 63;
	nth = 6;
	binary(m);
	cout << "   flip " << nth << "th bit of " << m << endl;
	bit_flip(m,nth);
	binary(m);

	return 0;
}
</pre>
<p>Output is:</p>
<pre>
   12: 0 0 0 0 1 1 0 0
   flip 2th bit of 12
    8: 0 0 0 0 1 0 0 0

   63: 0 0 1 1 1 1 1 1
   flip 6th bit of 63
  127: 0 1 1 1 1 1 1 1
</pre>
<br />
<br />


<div class="subtitle_2nd" id="floating_bit_pattern">Floating Point Number Bit Pattern</div>
<br />
<img src="images/quiz/floating_bit_pattern.png" alt="floating_bit_pattern"/>
<p><strong>Question A: What's the bit pattern of the following?</strong></p>
<pre>
int i = 25;
float f = *(float*)&i;
</pre>
<p>Note that the last line does not evaluate the <strong>value</strong> <i>i</i> but the <strong>location</strong> of <strong>i</strong>. So, whatever the bit pattern of the integer representing the address of <strong>i</strong> (<strong>&amp;i</strong>) considered as a bit pattern representing floating point number, <strong>*(float*)</strong>. </p>
<img src="images/quiz/very_small_number.png" alt="very_small_number"/>
<br />
<p><strong>Question B: What's the bit pattern of the following?</strong></p>
<pre>
float f = 25.0;
short s = *(short*)&f;
</pre>
<img src="images/quiz/short_number.png" alt="short_number"/>
<p>The <strong>&f</strong> is pointing to the starting address of 4 byte floating number. 
But when we cast it with <strong>(short*)&f</strong>, compiler thinks "I was wrong. 
The address is not representing a 4-byte floating point number but a short type." 
So, whatever bit pattern happend to reside in the first two bytes is now representing 2-byte short integer type. 
So, when we dereference it with <strong>*(short*)&f</strong>, we won't get the value we want which is 25.</p>
<br />
<br />


<div class="subtitle_2nd" id="int_palindrome">Bit pattern palindrome of an integer </div>
<p>Following example tells if the bit pattern of an interger is a palindrome or not. 
It first saves the integer to bitset, and the compare (xor) the bit pattern starting from both ends.</p>
<pre>
#include &lt;iostream&gt;
#include <font color="red">&lt;bitset&gt;</font>

using namespace std;

const int Max = 8*sizeof(int);

bool isPalindrome(int n)
{
	bool palindrome = true;
	bitset&lt;Max&gt; b = n;
	for(int i = 0; i < Max/2 - 1; i++) { 
		if(<font color="red">b[i] ^ b[Max-1-i]</font>) {
			palindrome = false;
			break;
		}
	}
	return palindrome;
}

int main()
{
	int m;
	m = (1 << (Max-1)) + (1 << 0);
	cout << bitset&lt;Max&gt; (m) << endl;
	cout << "palindrome: " << isPalindrome(m) << endl;

	m = (1 << (Max-1)) + (1 << 1);
	cout << bitset&lt;Max&gt; (m) << endl;
	cout << "palindrome: " << isPalindrome(m) << endl;

	m = (1 << (Max-2)) + (1 << 1);
	cout << bitset&lt;Max&gt; (m) << endl;
	cout << "palindrome: " << isPalindrome(m) << endl;

	m = (1 << (Max-6)) + (1 << 11);
	cout << bitset&lt;Max&gt; (m) << endl;
	cout << "palindrome: " << isPalindrome(m) << endl;

	m = (1 << (Max-2)) + (1 << (Max-3)) + (1 << 2) + (1 << 1);
	cout << bitset&lt;Max&gt; (m) << endl;
	cout << "palindrome: " << isPalindrome(m) << endl;

	return 0;
}
</pre>
<p>Output is:</p>
<pre>
10000000000000000000000000000001
palindrome: 1
10000000000000000000000000000010
palindrome: 0
01000000000000000000000000000010
palindrome: 1
00000100000000000000100000000000
palindrome: 0
01100000000000000000000000000110
palindrome: 1
</pre>
<br />
<br />
<br />
<img src="images/quiz/NaeSoSan.png" alt="NaeSoSan"/>
<br />
<br />
<br />
<div class="subtitle_2nd" id="FullList">Full List of C++ Tutorials</div>
<ul>
   <li><a href="cpptut.html">C++ Home</a> </li>
   <li><a href="string.html">String</a> </li>
   <li><a href="constructor.html">Constructor</a> </li>
   <li><a href="operatoroverloading.html">Operator Overloading</a></li> 
   <li><a href="virtualfunctions.html">Virtual Functions</a></li>
   <li><a href="dynamic_cast.html">Dynamic Cast Operator</a></li>
   <li><a href="typecast.html">Type Cast Operators</a></li>
   <li><a href="autoptr.html">Class auto_ptr</a></li>
   <li><a href="templates.html">Templates</a></li>
   <li><a href="references.html">References for Built-in Types</a></li>
   <li><a href="valuevsreference.html">Pass by Value vs. Pass by Reference</a></li>
   <li><a href="memoryallocation.html">Memory Allocation</a></li>
   <li><a href="friendclass.html">Friend Functions and Friend Classes</a></li>
   <li><a href="functors.html">Functors (Function Objects)</a></li>
   <li><a href="statics.html">Static Variables and Static Class Members</a></li>
   <li><a href="exceptions.html">Exceptions</a></li>
   <li><a href="pointers.html">Pointers</a></li>
   <li><a href="pointers2.html">Pointers II</a></li>
   <li><a href="pointers3.html">Pointers III</a></li>
   <li><a href="assembly.html">Taste of Assembly</a></li>
   <li><a href="smallprograms.html">Small Programs</a></li>
   <li><a href="linkedlist.html">Linked List Examples</a></li>
   <li><a href="stl.html">Standard Template Library (STL)</a></li>
   <li><a href="stl2.html">Standard Template Library (STL) II - Maps</a></li>
   <li><a href="stl3_iterators.html">Standard Template Library (STL) III - Iterators</a></li>
   <li><a href="slicing.html">Object Slicing and Virtual Table</a></li>
   <li><a href="this_pointer.html">The this Pointer</a></li>
   <li><a href="stackunwinding.html">Stack Unwinding</a></li>
   <li><a href="upcasting_downcasting.html">Upcasting and Downcasting</a></li>
   <li><a href="object_returning.html">Object Returning</a></li>
   <li><a href="private_inheritance.html">Private Inheritance</a></li>
   <li><a href="cplusplus_keywords.html">C++_Keywords</a></li>
   <li><a href="multithreaded.html">Multi-Threaded Programming - Terminology</a></li>
   <li><a href="multithreaded2A.html">Multi-Threaded Programming II - Native Thread for Win32 (A) </a></li>
   <li><a href="multithreaded2B.html">Multi-Threaded Programming II -  Native Thread for Win32 (B) </a></li>
   <li><a href="multithreaded2C.html">Multi-Threaded Programming II -  Native Thread for Win32 (C) </a></li>
   <li><a href="multithreaded2.html">Multi-Threaded Programming II - C++ Thread for Win32</a></li>
   <li><a href="multithreaded3.html">Multi-Threaded Programming III - C++ Class Thread for Pthreads</a></li>
   <li><a href="multithreadedDebugging.html">Multithread Debugging</a></li>
   <li><a href="embeddedSystemsProgramming.html">Embedded Systems Programming</a></li>
   <li><a href="boost.html">Boost</a></li>
   <li>Programming Questions and Solutions
    <ul>
       <li><a href="quiz_strings_arrays.html">Strings and Arrays</a></li>
       <li><a href="quiz_linkedlist.html">Linked List</a></li>
       <li><a href="quiz_recursion.html">Recursion</a></li>
       <li><a href="quiz_bit_manipulation.html">Bit Manipulation</a> 
       <li><a href="google_interview_questions.html">140 Google Interview Questions</a> </li>
    </ul>
   </li>

</ul>

<br />
<br />
<div id="rightpanel">
<div align="center">
</div></div>
<br />

<br />
</div>

<br />
<br />
<br />



<div class="smallgraytext" id="footer"><a href="../index.html">Home</a>
| <a href="../about_us.html">About Us</a>
| <a href="../products.html">products</a>
| <a href="../our_services.html">Our Services</a>
| <a href="#">Contact Us</a>
| Bogotobogo &copy; 2011 | <a target="_blank" href="http://www.bogotobogo.com">Bogotobogo </a></div>
</div>
</div>
</body>
</html>

